{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Running Time of N Computers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxRunTime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #同时运行 N 台电脑的最长时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你有&nbsp;<code>n</code>&nbsp;台电脑。给你整数&nbsp;<code>n</code>&nbsp;和一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>batteries</code>&nbsp;，其中第&nbsp;<code>i</code>&nbsp;个电池可以让一台电脑 <strong>运行&nbsp;</strong><code>batteries[i]</code>&nbsp;分钟。你想使用这些电池让&nbsp;<strong>全部</strong>&nbsp;<code>n</code>&nbsp;台电脑 <b>同时</b>&nbsp;运行。</p>\n",
    "\n",
    "<p>一开始，你可以给每台电脑连接 <strong>至多一个电池</strong>&nbsp;。然后在任意整数时刻，你都可以将一台电脑与它的电池断开连接，并连接另一个电池，你可以进行这个操作 <strong>任意次</strong>&nbsp;。新连接的电池可以是一个全新的电池，也可以是别的电脑用过的电池。断开连接和连接新的电池不会花费任何时间。</p>\n",
    "\n",
    "<p>注意，你不能给电池充电。</p>\n",
    "\n",
    "<p>请你返回你可以让 <code>n</code>&nbsp;台电脑同时运行的 <strong>最长</strong>&nbsp;分钟数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/01/06/example1-fit.png\" style=\"width: 762px; height: 150px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>n = 2, batteries = [3,3,3]\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>\n",
    "一开始，将第一台电脑与电池 0 连接，第二台电脑与电池 1 连接。\n",
    "2 分钟后，将第二台电脑与电池 1 断开连接，并连接电池 2 。注意，电池 0 还可以供电 1 分钟。\n",
    "在第 3 分钟结尾，你需要将第一台电脑与电池 0 断开连接，然后连接电池 1 。\n",
    "在第 4 分钟结尾，电池 1 也被耗尽，第一台电脑无法继续运行。\n",
    "我们最多能同时让两台电脑同时运行 4 分钟，所以我们返回 4 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/01/06/example2.png\" style=\"width: 629px; height: 150px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>n = 2, batteries = [1,1,1,1]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>\n",
    "一开始，将第一台电脑与电池 0 连接，第二台电脑与电池 2 连接。\n",
    "一分钟后，电池 0 和电池 2 同时耗尽，所以你需要将它们断开连接，并将电池 1 和第一台电脑连接，电池 3 和第二台电脑连接。\n",
    "1 分钟后，电池 1 和电池 3 也耗尽了，所以两台电脑都无法继续运行。\n",
    "我们最多能让两台电脑同时运行 2 分钟，所以我们返回 2 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= batteries.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= batteries[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-running-time-of-n-computers](https://leetcode.cn/problems/maximum-running-time-of-n-computers/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-running-time-of-n-computers](https://leetcode.cn/problems/maximum-running-time-of-n-computers/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n[3,3,3]', '2\\n[1,1,1,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        m = len(batteries)\n",
    "        if m == n:\n",
    "            return min(batteries)\n",
    "        batteries.sort()\n",
    "        live = [0] * n\n",
    "        \n",
    "        for i in range(n):\n",
    "            live[i] = batteries[i + m - n]\n",
    "        extra = 0\n",
    "        for i in range(m - n):\n",
    "            extra += batteries[i]\n",
    "        for i in range(1, n ):\n",
    "            gap = live[i] - live[i - 1]\n",
    "            if i * gap <= extra: # can \n",
    "                extra -= i * gap\n",
    "            else:\n",
    "                return live[i - 1] + extra // i\n",
    "        return live[n - 1] + extra // n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        batteries.sort(reverse=True)\n",
    "        s = sum(batteries)\n",
    "        for b in batteries:\n",
    "            if b <= s // n: return s // n\n",
    "            s -= b\n",
    "            n -= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "\n",
    "        batteries.sort(reverse = True)\n",
    "        sum_bat = sum(batteries)\n",
    "        for i in batteries:\n",
    "            if i <= sum_bat//n:\n",
    "                return sum_bat // n\n",
    "            sum_bat -= i\n",
    "            n -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        batteries.sort(reverse=True)\n",
    "        s = sum(batteries)\n",
    "        for b in batteries:\n",
    "            if b<=s//n:\n",
    "                return s//n\n",
    "            s -= b\n",
    "            n -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        s = sum(batteries)\n",
    "        batteries.sort()\n",
    "        while batteries:\n",
    "            b = batteries[-1]\n",
    "            if b > s // n:\n",
    "                s -= batteries.pop()\n",
    "                n -= 1 \n",
    "            else:\n",
    "                return s // n "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        l, r = 0, sum(batteries) // n\n",
    "        def check(mid):\n",
    "            s = 0\n",
    "            for x in batteries:\n",
    "                s += min(x, mid)\n",
    "            return s >= n * mid\n",
    "        while l < r:\n",
    "            mid = l + r + 1 >> 1\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else: r = mid - 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        batteries.sort(reverse=True)\n",
    "        s = sum(batteries)\n",
    "        for b in batteries:\n",
    "            if b <= s // n: return s // n\n",
    "            s -= b\n",
    "            n -= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        s = sum(batteries)\n",
    "        batteries.sort()\n",
    "        while batteries:\n",
    "            b = batteries[-1]\n",
    "            if b > s // n:\n",
    "                s -= batteries.pop()\n",
    "                n -= 1 \n",
    "            else:\n",
    "                return s // n "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    @staticmethod\n",
    "    def maxRunTime(num: int, arr: List[int]) -> int:\n",
    "        max_val = 0\n",
    "        total_sum = 0\n",
    "\n",
    "        # 计算数组中的最大值和总和\n",
    "        for x in arr:\n",
    "            max_val = max(max_val, x)\n",
    "            total_sum += x\n",
    "\n",
    "        # 如果总和大于等于最大值乘以电池数量\n",
    "        if total_sum >= max_val * num:\n",
    "            # 所有电池的最大电量是 max_val\n",
    "            # 如果总和大于等于 max_val * num，\n",
    "            # 说明最终的供电时间一定在 >= max_val，而如果最终的供电时间 >= max_val\n",
    "            # 说明对于最终的答案 X，所有电池都是碎片拼接的概念\n",
    "            # 所以寻找 ? * num <= total_sum 的情况中，尽量大的 ? 即可\n",
    "            # 即 total_sum // num\n",
    "            return total_sum // num\n",
    "\n",
    "        # 最终的供电时间一定在 < max_val 范围上\n",
    "        # [0, total_sum] 二分范围，可能定的比较粗，虽然不影响，但毕竟是有点慢\n",
    "        # [0, max_val] 二分范围！更精细的范围，二分次数会变少\n",
    "        ans = 0\n",
    "        l, r = 0, max_val\n",
    "\n",
    "        while l <= r:\n",
    "            m = l + ((r - l) >> 1)\n",
    "            if Solution.f2(arr, num, m):\n",
    "                ans = m\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m - 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "    @staticmethod\n",
    "    def f2(arr: List[int], num: int, time: int) -> bool:\n",
    "        # 碎片电量总和\n",
    "        total_sum = 0\n",
    "\n",
    "        for x in arr:\n",
    "            if x > time:\n",
    "                num -= 1\n",
    "            else:\n",
    "                total_sum += x\n",
    "\n",
    "            if total_sum >= num * time:\n",
    "                return True\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        batteries.sort(reverse=True)\n",
    "        s = sum(batteries)\n",
    "        for b in batteries:\n",
    "            if b <= s // n:\n",
    "                return s // n\n",
    "            s -= b \n",
    "            n -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        start = ans = 0\n",
    "        end = 9223372036854775807\n",
    "        while start <= end:\n",
    "            mid = start + ((end-start) >> 1)\n",
    "            t = mid\n",
    "            c = 0\n",
    "            for i in batteries:\n",
    "                if i >= mid:\n",
    "                    c += 1\n",
    "                elif t - i > 0:\n",
    "                    t -= i\n",
    "                elif t - i <= 0:\n",
    "                    t = mid - i + t\n",
    "                    c += 1\n",
    "            \n",
    "            if c >= n:\n",
    "                ans = mid\n",
    "                start = mid + 1\n",
    "            else:\n",
    "                end = mid - 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        l, r = 0, sum(batteries) // n\n",
    "        while l < r:\n",
    "            x = (l + r + 1) // 2\n",
    "            if n * x <= sum(min(b, x) for b in batteries):\n",
    "                l = x\n",
    "            else:\n",
    "                r = x - 1\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BinarySearch:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def find_int_left(low: int, high: int, check: Callable) -> int:\n",
    "        # 模板: 整数范围内二分查找，选择最靠左满足check\n",
    "        while low < high - 1:\n",
    "            mid = low + (high - low) // 2\n",
    "            if check(mid):\n",
    "                high = mid\n",
    "            else:\n",
    "                low = mid\n",
    "        return low if check(low) else high\n",
    "\n",
    "    @staticmethod\n",
    "    def find_int_right(low: int, high: int, check: Callable) -> int:\n",
    "        # 模板: 整数范围内二分查找，选择最靠右满足check\n",
    "        while low < high - 1:\n",
    "            mid = low + (high - low) // 2\n",
    "            if check(mid):\n",
    "                low = mid\n",
    "            else:\n",
    "                high = mid\n",
    "        return high if check(high) else low\n",
    "\n",
    "    @staticmethod\n",
    "    def find_float_left(low: float, high: float, check: Callable, error=1e-6) -> float:\n",
    "        # 模板: 浮点数范围内二分查找, 选择最靠左满足check\n",
    "        while low < high - error:\n",
    "            mid = low + (high - low) / 2\n",
    "            if check(mid):\n",
    "                high = mid\n",
    "            else:\n",
    "                low = mid\n",
    "        return low if check(low) else high\n",
    "\n",
    "    @staticmethod\n",
    "    def find_float_right(low: float, high: float, check: Callable, error=1e-6) -> float:\n",
    "        # 模板: 浮点数范围内二分查找, 选择最靠右满足check\n",
    "        while low < high - error:\n",
    "            mid = low + (high - low) / 2\n",
    "            if check(mid):\n",
    "                low = mid\n",
    "            else:\n",
    "                high = mid\n",
    "        return high if check(high) else low\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        batteries.sort(reverse=True)\n",
    "        rest = sum(batteries[n:])\n",
    "\n",
    "        def check(w):\n",
    "            res = 0\n",
    "            for num in batteries[:n]:\n",
    "                if num < w:\n",
    "                    res += w-num\n",
    "            return res <= rest\n",
    "\n",
    "        return BinarySearch().find_int_right(0, batteries[n-1]+rest, check)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        batteries.sort(reverse=True)\n",
    "        s = sum(batteries)\n",
    "        for battery in batteries:\n",
    "            t = s // n\n",
    "            if battery <= t:\n",
    "                return t\n",
    "            s -= battery\n",
    "            n -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        l=0\n",
    "        r=sum(batteries)//n\n",
    "        batteries.sort(reverse=True)\n",
    "        def check(x):\n",
    "            need=n*x\n",
    "            for batterie in batteries:\n",
    "                if batterie>=x:\n",
    "                    need-=x\n",
    "                else:\n",
    "                    need-=batterie\n",
    "                if need<=0:\n",
    "                    return True\n",
    "            return False\n",
    "        while l<r:\n",
    "            mid=(l+r)//2\n",
    "            if check(mid):\n",
    "                l=mid\n",
    "            else:\n",
    "                r=mid-1\n",
    "            if r-l==1:\n",
    "                if check(r):\n",
    "                    return r\n",
    "                else:\n",
    "                    return l\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "      l, r = 1, 10 ** 15\n",
    "      while l < r:\n",
    "        mid = l + r + 1 >> 1\n",
    "        if sum(min(mid, x) for x in batteries) >= mid * n:\n",
    "          l = mid\n",
    "        else:\n",
    "          r = mid - 1\n",
    "      return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        l, r = 0, sum(batteries) // n\n",
    "        while l <= r:\n",
    "            m = l + r >> 1\n",
    "            cnt = tot = 0\n",
    "            for b in batteries:\n",
    "                if b >= m:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    tot += b\n",
    "                    if tot >= m:\n",
    "                        tot -= m\n",
    "                        cnt += 1\n",
    "            if cnt >= n:\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m - 1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        batteries.sort(reverse = True)\n",
    "        s = sum(batteries)\n",
    "        for b in batteries:\n",
    "            if b <= s // n: return s // n\n",
    "            s -= b\n",
    "            n -= 1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "\n",
    "        def f(batteries,m,n):\n",
    "            sum1 = 0\n",
    "            for num in batteries:\n",
    "                if num>m:\n",
    "                    n -= 1\n",
    "                else:\n",
    "                    sum1 += num\n",
    "                if sum1>=n*m:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "\n",
    "        l = 0\n",
    "        r = sum(batteries)\n",
    "        ans = 0\n",
    "        while l<=r:\n",
    "            m = l+((r-l)>>1)\n",
    "            if f(batteries,m,n):\n",
    "                ans = m\n",
    "                l = m+1\n",
    "            else:\n",
    "                r = m-1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        left, right = 0, sum(batteries) // n + 1\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if mid * n <= sum(min(mid, battery) for battery in batteries):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        s = sum(batteries)\n",
    "        batteries.sort(reverse=True)\n",
    "        for it in batteries:\n",
    "            if it <= s // n:\n",
    "                return s//n\n",
    "            s -= it\n",
    "            n -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        batteries.sort(reverse=True)\n",
    "        s = sum(batteries)\n",
    "        for b in batteries:\n",
    "            if b <= s // n: return s // n\n",
    "            s -= b\n",
    "            n -= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: list[int]) -> int:\n",
    "        left, right = 0, sum(batteries)\n",
    "        if n == 1:\n",
    "            return sum(batteries)\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            # check\n",
    "            if mid * n <= sum([min(mid, b) for b in batteries]):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    @staticmethod\n",
    "    def maxRunTime(num: int, arr: List[int]) -> int:\n",
    "        max_val = 0\n",
    "        total_sum = 0\n",
    "\n",
    "        # 计算数组中的最大值和总和\n",
    "        for x in arr:\n",
    "            max_val = max(max_val, x)\n",
    "            total_sum += x\n",
    "\n",
    "        # 如果总和大于等于最大值乘以电池数量\n",
    "        if total_sum >= max_val * num:\n",
    "            # 所有电池的最大电量是 max_val\n",
    "            # 如果总和大于等于 max_val * num，\n",
    "            # 说明最终的供电时间一定在 >= max_val，而如果最终的供电时间 >= max_val\n",
    "            # 说明对于最终的答案 X，所有电池都是碎片拼接的概念\n",
    "            # 所以寻找 ? * num <= total_sum 的情况中，尽量大的 ? 即可\n",
    "            # 即 total_sum // num\n",
    "            return total_sum // num\n",
    "\n",
    "        # 最终的供电时间一定在 < max_val 范围上\n",
    "        # [0, total_sum] 二分范围，可能定的比较粗，虽然不影响，但毕竟是有点慢\n",
    "        # [0, max_val] 二分范围！更精细的范围，二分次数会变少\n",
    "        ans = 0\n",
    "        l, r = 0, max_val\n",
    "\n",
    "        while l <= r:\n",
    "            m = l + ((r - l) >> 1)\n",
    "            if Solution.f2(arr, num, m):\n",
    "                ans = m\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m - 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "    @staticmethod\n",
    "    def f2(arr: List[int], num: int, time: int) -> bool:\n",
    "        # 碎片电量总和\n",
    "        total_sum = 0\n",
    "\n",
    "        for x in arr:\n",
    "            if x > time:\n",
    "                num -= 1\n",
    "            else:\n",
    "                total_sum += x\n",
    "\n",
    "            if total_sum >= num * time:\n",
    "                return True\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        start = ans = 0\n",
    "        end = 9223372036854775807\n",
    "        while start <= end:\n",
    "            mid = start + ((end-start) >> 1)\n",
    "            t = mid\n",
    "            c = 0\n",
    "            for i in batteries:\n",
    "                if i >= mid:\n",
    "                    c += 1\n",
    "                elif t - i > 0:\n",
    "                    t -= i\n",
    "                elif t - i <= 0:\n",
    "                    t = mid - i + t\n",
    "                    c += 1\n",
    "                if c >= n:\n",
    "                    break\n",
    "            \n",
    "            if c >= n:\n",
    "                ans = mid\n",
    "                start = mid + 1\n",
    "            else:\n",
    "                end = mid - 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        def f(n, batteries, target):\n",
    "            cur_sum = 0\n",
    "            for i in range(len(batteries)):\n",
    "                if batteries[i]>target:\n",
    "                    n -= 1\n",
    "                else:\n",
    "                    cur_sum += batteries[i]\n",
    "            # print(cur_sum, n*target)\n",
    "            return cur_sum>=n*target\n",
    "\n",
    "        cur_sum = 0\n",
    "        for i in range(len(batteries)):\n",
    "            cur_sum += batteries[i]\n",
    "        if cur_sum>=n*max(batteries):\n",
    "            return cur_sum//n\n",
    "        else:\n",
    "            l = 0\n",
    "            r = max(batteries)\n",
    "        while l<=r: \n",
    "            mid = l+(r-l)//2\n",
    "            if f(n, batteries, mid):\n",
    "                ans = mid\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def f(self, batteries, num, time):\n",
    "        s = 0\n",
    "        for battery in batteries:\n",
    "            if battery > time:\n",
    "                num -= 1\n",
    "            else:\n",
    "                s += battery\n",
    "            if s >= num * time:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        left, right = 0, sum(batteries)\n",
    "        res = 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if self.f(batteries, n, mid):\n",
    "                res = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        # 1. 贪心策略： 对电池电量从大到小排序，然后从电量最大的电池开始遍历\n",
    "        # batteries.sort(reverse = True)\n",
    "        # s = sum(batteries)\n",
    "        # for b in batteries:\n",
    "        #     if b <= s // n: return s // n\n",
    "        #     s -= b\n",
    "        #     n -= 1\n",
    "\n",
    "        # 2. 二分： 如果可以让n台电脑同时云心x分钟，那必然可以同时运行低于x分钟，满足单调性\n",
    "        l, r = 0, sum(batteries) // n\n",
    "        while l < r:\n",
    "            x = (l + r + 1) // 2\n",
    "            if n * x <= sum(min(b, x) for b in batteries):\n",
    "                l = x\n",
    "            else:\n",
    "                r = x - 1\n",
    "        return l \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        def f(m):\n",
    "            s = 0\n",
    "            x = n\n",
    "            for b in batteries:\n",
    "                if b>m:\n",
    "                    x -= 1\n",
    "                else:\n",
    "                    s += b\n",
    "                if s>=x*m:\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        # batteries.sort(reverse=True)\n",
    "        l,r = 0,sum(batteries)//n\n",
    "        while l<=r:\n",
    "            m = (l+r)//2\n",
    "            if f(m):\n",
    "                ans = m\n",
    "                l = m+1\n",
    "            else:\n",
    "                r = m-1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        N = len(batteries)\n",
    "        if N < n:return 0\n",
    "        if n == 1:return sum(batteries)\n",
    "        def check(k):\n",
    "            s = 0\n",
    "            for i in batteries:\n",
    "                s += i if i <= k else k\n",
    "            return s < n*k\n",
    "        return bisect_left(range(10**15),True,key = check)-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        l,r = 0, (sum(batteries)//n)+1\n",
    "\n",
    "        def check(k):\n",
    "            s = sum([min(k,batteries[i]) for i in range(len(batteries))])\n",
    "            if n*k<=s:\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        res = 0\n",
    "        while l<=r:\n",
    "            mid = (l+r)//2\n",
    "            if check(mid):\n",
    "                res = mid\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        l,r=0,sum(batteries)\n",
    "        while l<r:\n",
    "            x=(l+r+1)//2\n",
    "            if n*x <= sum(min(b,x) for b in batteries):\n",
    "                l=x\n",
    "            else:\n",
    "                r=x-1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        l, r = 0, sum(batteries) // n\n",
    "        while l < r:\n",
    "            x = (l + r + 1) // 2\n",
    "            if n * x <= sum(min(b, x) for b in batteries):\n",
    "                l = x\n",
    "            else:\n",
    "                r = x - 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        left, right, ans = 0, sum(batteries) // n, 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            total = 0\n",
    "            for cap in batteries:\n",
    "                total += min(cap, mid)\n",
    "            if total >= n * mid:\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "\n",
    "\n",
    "        l, r, res = 0, sum(batteries) // n, 0\n",
    "\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            total = 0\n",
    "\n",
    "            for cap in batteries:\n",
    "\n",
    "                total += min(cap, mid)\n",
    "            \n",
    "            if total >= n * mid:\n",
    "                res = mid\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        l, r = 0, sum(batteries) // n\n",
    "        while l < r:\n",
    "            x = (l + r + 1) // 2\n",
    "            if n * x <= sum(min(b, x) for b in batteries):\n",
    "                l = x\n",
    "            else:\n",
    "                r = x - 1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        def check(x):\n",
    "            s = sum(min(b, x) for b in batteries)\n",
    "            if s >= n*x:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        \n",
    "        left =  0\n",
    "        right = sum(batteries) // n + 1\n",
    "        while left < right:\n",
    "            mid = (left+right)//2\n",
    "            if check(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        S = sum(batteries)\n",
    "        if S > max(batteries) * n:\n",
    "            return S // n\n",
    "        l, r = 0, max(batteries) + 1\n",
    "        while l < r:\n",
    "            x = (l + r + 1) // 2\n",
    "            if n * x <= sum(min(b, x) for b in batteries):\n",
    "                l = x\n",
    "            else:\n",
    "                r = x - 1\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        S = sum(batteries)\n",
    "        if S > max(batteries) * n:\n",
    "            return S // n\n",
    "        l, r = 0, S // n\n",
    "        while l < r:\n",
    "            x = (l + r + 1) // 2\n",
    "            if n * x <= sum(min(b, x) for b in batteries):\n",
    "                l = x\n",
    "            else:\n",
    "                r = x - 1\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        # 大概率是二分，具有单调边界\n",
    "        # 问题在于怎样判断行不行，最次都用时间最多的n个\n",
    "        # 但是数据范围会比较大，所以需要好好斟酌一下\n",
    "        def check(t):\n",
    "            nums = [min(b, t) for b in batteries]\n",
    "            return sum(nums) < t*n\n",
    "            \n",
    "        return bisect_left(range(10**14+1), True, key=check) - 1\n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        l, r = min(batteries), 10 ** 15\n",
    "        ans = -1\n",
    "        # batteries.sort(reverse=True)\n",
    "\n",
    "        def check(num):\n",
    "            # 能不能在这个时候让n台电脑同时运行 贪心地思考什么\n",
    "            return sum(min(now, num) for now in batteries) >= num * n\n",
    "\n",
    "        while l <= r:\n",
    "            mid = l + r >> 1\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        l,r = 0,sum(batteries)//n\n",
    "        while l < r:\n",
    "            mid = (l + r + 1) // 2\n",
    "            if mid * n <= sum(min(b,mid) for b in batteries):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        def f(n, batteries, target):\n",
    "            cur_sum = 0\n",
    "            for i in range(len(batteries)):\n",
    "                if  batteries[i]>=target:\n",
    "                    n -= 1\n",
    "                else:\n",
    "                    cur_sum += batteries[i]\n",
    "            # print(cur_sum, n*target)\n",
    "            return cur_sum>=n*target\n",
    "\n",
    "        l = 0\n",
    "        r = sum(batteries)\n",
    "        while l<=r: \n",
    "            mid = l+(r-l)//2\n",
    "            if f(n, batteries, mid):\n",
    "                ans = mid\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        l = 0 \n",
    "        r = sum(batteries)//n\n",
    "        while l<r:\n",
    "            mid = l+(r-l+1)//2\n",
    "            if mid * n <= sum(min(mid, b) for b in batteries):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "\n",
    "\n",
    "        left, right, ans = 0, sum(batteries) // n, 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            total = 0\n",
    "            for cap in batteries:\n",
    "                total += min(cap, mid)\n",
    "            if total >= n * mid:\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "\n",
    "        def f(batteries,m,n):\n",
    "            sum1 = 0\n",
    "            for num in batteries:\n",
    "                if num>m:\n",
    "                    n -= 1\n",
    "                else:\n",
    "                    sum1 += num\n",
    "                if sum1>=n*m:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        if sum(batteries)>max(batteries)*n:\n",
    "            return sum(batteries)//n\n",
    "        l = 0\n",
    "        r = max(batteries)\n",
    "        ans = 0\n",
    "        while l<=r:\n",
    "            m = l+((r-l)>>1)\n",
    "            if f(batteries,m,n):\n",
    "                ans = m\n",
    "                l = m+1\n",
    "            else:\n",
    "                r = m-1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        def f(n, batteries, target):\n",
    "            cur_sum = 0\n",
    "            for i in range(len(batteries)):\n",
    "                if batteries[i]>target:\n",
    "                    n -= 1\n",
    "                else:\n",
    "                    cur_sum += batteries[i]\n",
    "            # print(cur_sum, n*target)\n",
    "            return cur_sum>=n*target\n",
    "\n",
    "        cur_sum = 0\n",
    "        for i in range(len(batteries)):\n",
    "            cur_sum += batteries[i]\n",
    "        if cur_sum>=n*max(batteries):\n",
    "            return cur_sum//n\n",
    "        else:\n",
    "            l = 0\n",
    "            r = max(batteries)\n",
    "        while l<=r: \n",
    "            mid = l+(r-l)//2\n",
    "            if f(n, batteries, mid):\n",
    "                ans = mid\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        batteries.sort(reverse = True)\n",
    "        total = sum(batteries)\n",
    "        cn = n\n",
    "        i=0 \n",
    "        N = len(batteries)\n",
    "        curMax = float(\"inf\")\n",
    "        while i<N and batteries[i]>total//cn:\n",
    "            curMax = min(curMax,total//cn)\n",
    "            total-=batteries[i]\n",
    "            i+=1\n",
    "            cn-=1\n",
    "        curMax = min(curMax,total//cn)\n",
    "        return curMax\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "\n",
    "        def check(mid):\n",
    "            cnt = 0\n",
    "            re = 0\n",
    "            for b in batteries:\n",
    "                if b >= mid:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    re += b\n",
    "            t = re // mid\n",
    "            cnt += t\n",
    "            return cnt >= n\n",
    "\n",
    "        return bisect_left(range(sum(batteries) // n + 1), 1, 1, key=lambda t: not check(t)) - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        l , r = 0 , sum(batteries)\n",
    "        while l < r:\n",
    "            mid = (l + r + 1) >> 1\n",
    "            if n * mid <= sum([min(x,mid) for x in batteries]):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        def check(batteries, n, time):\n",
    "            sumx = 0\n",
    "            for i in range(len(batteries)):\n",
    "                if batteries[i] >= time:\n",
    "                    n -= 1\n",
    "                else:\n",
    "                    sumx += batteries[i]\n",
    "            if sumx >= n * time:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        l = 0\n",
    "        r = sum(batteries)\n",
    "        ans = 0\n",
    "        while l <= r:\n",
    "            mid = (l+r) // 2\n",
    "            if check(batteries, n, mid):\n",
    "                ans = mid\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1 \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        l, r = min(batteries), sum(batteries)\n",
    "        ans = -1\n",
    "        # batteries.sort(reverse=True)\n",
    "\n",
    "        def check(num):\n",
    "            # 能不能在这个时候让n台电脑同时运行 贪心地思考什么\n",
    "            return sum(min(now, num) for now in batteries) >= num * n\n",
    "\n",
    "        while l <= r:\n",
    "            mid = l + r >> 1\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        l, r, ans = 0, sum(batteries) // n, 0\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            total = 0\n",
    "            for bat in batteries:\n",
    "                total += min(bat, mid)\n",
    "            if total >= n * mid:\n",
    "                ans = mid\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        l = 0\n",
    "        r = sum(batteries) // n\n",
    "        while l <= r:\n",
    "            m = (l+r) // 2\n",
    "            if sum([min(m, i) for i in batteries]) < m*n:\n",
    "                r = m-1\n",
    "            else:\n",
    "                l = m+1\n",
    "\n",
    "        return l-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "        be, af = 1, sum(batteries) // n + 1\n",
    "        def check(batteries, n, mid):\n",
    "            s = 0\n",
    "            for bat in batteries:\n",
    "                s += min(mid, bat)\n",
    "            return s >= n*mid\n",
    "\n",
    "        while be < af:\n",
    "            mid = (be + af) // 2\n",
    "            if check(batteries, n, mid):\n",
    "                be = mid + 1\n",
    "            else:\n",
    "                af = mid\n",
    "        return be - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "\n",
    "\n",
    "        l, r, res = 0, sum(batteries) // n, 0\n",
    "\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            total = 0\n",
    "\n",
    "            for cap in batteries:\n",
    "\n",
    "                total += min(cap, mid)\n",
    "            \n",
    "            if total >= n * mid:\n",
    "                res = mid\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRunTime(self, n: int, batteries: List[int]) -> int:\n",
    "\n",
    "        batteries.sort()\n",
    "        m=len(batteries)\n",
    "        if m==n:return min(batteries)\n",
    "        last=sum(batteries[:m-n])\n",
    "        bt=batteries[m-n:]\n",
    "        print(last,bt)\n",
    "\n",
    "        def check(mid):\n",
    "            cnt=0\n",
    "            cur=last\n",
    "            for v in bt:\n",
    "                if v>mid:return True\n",
    "                if v+cur<mid:return False\n",
    "                cur-=mid-v\n",
    "            return True\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "        l,r=min(batteries),sum(batteries)\n",
    "        while l<r:\n",
    "            mid=l+r+1>>1\n",
    "            if check(mid):\n",
    "                l=mid\n",
    "            else:\n",
    "                r=mid-1\n",
    "        return r"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
